#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

void pathNumCore(BinaryTreeNode* root, int path, map<int, int> help_map, const int& value, int &path_num) {
  if (!root) {
    return;
  }
  path += root->value;
  int target_num = path - value;
  if (help_map.find(target_num) != help_map.end()) {
    path_num += help_map[target_num];
  }

  if (help_map.find(path) != help_map.end()) {
    ++help_map[path];
  } else {
    help_map[path] = 1;
  }

  pathNumCore(root->left, path, help_map, value, path_num);
  pathNumCore(root->right, path, help_map, value, path_num);

  path -= root->value;
  help_map[path]--;
}

int pathNum(BinaryTreeNode* root, int value) {
  int path = 0;
  int path_num = 0;
  map<int, int> help_map;
  help_map[0] = 1;
  pathNumCore(root, path, help_map, value, path_num);
  return path_num;
}

int main() {
  vector<int> vec = {5, 2, 4, 1, 6, 3, 7};
  int value = 8;
  BinaryTreeNode* root = CreateBinaryTree(vec);
  int ret = pathNum(root, value);
  cout << ret << endl;

  return 0;
}
